package 二叉树;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

//二叉树的基本操作
class TreeNode{
    public char val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode(char val1) {
        this.val = val1;
    }
}
public class BinaryTree {
    public TreeNode createTree() {
        TreeNode a = new TreeNode('A');
        TreeNode b = new TreeNode('B');
        TreeNode c = new TreeNode('C');
        TreeNode d = new TreeNode('D');
        TreeNode e = new TreeNode('E');
        TreeNode f = new TreeNode('F');
        TreeNode g = new TreeNode('G');
        TreeNode h = new TreeNode('H');

        a.left = b;
        a.right = c;
        b.left = d;
        b.right = e;
        c.left = f;
        c.right = g;
        e.right = h;

        return a;
    }

    //前序遍历
    public void preOrderTraversal(TreeNode root) {
        if (root == null) {
            return;
        }
        System.out.print(root.val + " ");
        preOrderTraversal(root.left);
        preOrderTraversal(root.right);

    }

    //中序遍历
    public void inOrderTraversal(TreeNode root) {
        if (root == null) {
            return;
        }
        inOrderTraversal(root.left);
        System.out.print(root.val + " ");
        inOrderTraversal(root.right);

    }

    //后序遍历
    public void postOrderTraversal(TreeNode root) {
        if (root == null) {
            return;
        }
        postOrderTraversal(root.left);
        postOrderTraversal(root.right);
        System.out.print(root.val + " ");

    }

    //遍历思想——求节点个数   O(n)
    static int size = 0;

    void getSize1(TreeNode root) {
        if (root == null) {
            return;
        }
        //用 前序 遍历
        size++;
        getSize1(root.left);
        getSize1(root.right);
    }

    //子问题 根+左子树+右子树思想——求节点个数  O(n)
    int getSize2(TreeNode root) {
        if (root == null) {
            return 0;
        }

        return getSize2(root.left) + getSize2(root.right) + 1;
    }

    //遍历思路——求叶子节点个数
    static int leafSize = 0;

    void getLeafSize1(TreeNode root) {
        if (root == null) {
            return;
        }
        //遍历二叉树，只要节点的左子树和右子树为空，则 leafSize++
        if (root.right == null && root.left == null) {
            leafSize++;
            return;
        }
        getLeafSize1(root.left);
        getLeafSize1(root.right);
    }


    //子问题思路 左树叶子节点+右树叶子节点——求叶子节点个数
    int getLeafSize2(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.left == null) {
            return 1;
        }
        return getLeafSize2(root.left) + getLeafSize2(root.right);
    }

    //子问题思路——求 K 层 节点个数
    int getKLevelSize(TreeNode root, int k) {
        if (root == null) {
            return 0;
        }
        if (k == 1) {
            return 1;
        }
        //k 不等于 1 就进入递归
        return getKLevelSize(root.left, k - 1) + getKLevelSize(root.right, k - 1);
    }

    //二叉树中查找某个节点——遍历查找可以解决，不考虑重复节点
    //二叉树中查找某个节点——子问题思路，不考虑重复节点
    TreeNode find(TreeNode root, char val) {
        if (root == null) {
            return null;
        }
        if (root.val == val) {
            return root;
        }
        TreeNode res = find(root.left, val);
        if (res != null) {
            return res;
        }
        TreeNode res2 = find(root.right, val);
        if (res2 != null) {
            return res2;
        }

        return null;
    }

    //子问题思路——求二叉树的高度
    //高度=Max(当前root的左子树高度+当前root的右子树高度) +1
    int getHeight(TreeNode root) {
        if (root == null) {
            return 0;
        }
        //当root不为空，开始深入递归
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        return Math.max(leftHeight + 1, rightHeight + 1);
    }

    //层序遍历
    void levelOrderTraversal(TreeNode root) {
        if (root == null) {
            return;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            //队列不为空，出队头元素+判断元素左右情况
            TreeNode top = queue.poll();//弹出队头元素
            System.out.print(top.val + " ");//打印队头元素

            if (top.left != null) {
                queue.offer(top.left);
            }
            if (top.right != null) {
                queue.offer(top.right);
            }
        }
        System.out.println();
    }

    //判断一棵树是不是 完全二叉树
    boolean isCompleteTree(TreeNode root) {
        if (root == null) {
            return true;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode top = queue.poll();
            if (top != null) {
                queue.offer(top.left);
                queue.offer(top.right);
            } else {
                break;//队头为空，结束循环，开始判断是否为 完全二叉树
            }
        }
        while (!queue.isEmpty()) {

            TreeNode top2=queue.poll();
//            if (top2==null) {
//                queue.poll();//如果当前队头元素为空，继续判断后面的
//            }else {
//                return false;//当前队头元素不为空，则不是 完全二叉树！！！
//            }
            if (top2!=null) {
                //当前队头元素不为空，则不是 完全二叉树！！！
                return false;
            }
        }
        return true;//是 完全二叉树
    }

    //递归是由栈实现的，因此非递归需要创建栈实现，利用栈模拟递归的路线，再合适的时机进行打印
    //非递归的前序遍历
    void preOrderTraversalNor(TreeNode root) {
        if (root==null) return;

        Stack<TreeNode> stack=new Stack<>();
        TreeNode cur=root;

        while (cur!=null || !stack.isEmpty()){
            while (cur!=null) {
                stack.push(cur);
                System.out.print(cur.val+" ");
                cur=cur.left;
            }
            TreeNode top=stack.pop();//弹出栈顶元素,判断栈顶元素的右树情况
            cur=top.right;
        }
        System.out.println();
    }

    //非递归的中序遍历
    void inOrderTraversalNor(TreeNode root) {
        if (root==null) return;
        Stack<TreeNode> stack=new Stack<>();
        TreeNode cur=root;

        while (cur!=null || !stack.isEmpty()) {
            while (cur!=null) {
                stack.push(cur);
                cur=cur.left;
            }
            TreeNode top=stack.pop();
            System.out.print(top.val+" ");
            cur=top.right;
        }
        System.out.println();
    }
    //非递归的后序遍历
    void postOrderTraversalNor(TreeNode root) {
        if (root==null) return;
        Stack<TreeNode> stack=new Stack<>();

        TreeNode cur=root;
        TreeNode pre=null;

        while (cur!=null || !stack.isEmpty()) {
            while (cur!=null) {
                stack.push(cur);
                cur=cur.left;
            }
            cur=stack.peek();
            if (cur.right==null || cur.right==pre) {
                TreeNode pop=stack.pop();
                System.out.println(pop.val+" ");
                pre=cur;
                cur=null;
            }else {
                cur=cur.right;
            }
        }



    }





}
